1. Technical Field
The invention relates to data input devices. More particularly, the invention relates to a spell-check mechanism for a keyboard system having automatic correction capability.
2. Description of the Prior Art
Classic spell-check (“Edit Distance”) techniques for transposed/added/dropped characters have a relatively long history. See, for example, Kukich, K., Techniques for Automatically Correcting Words, ACM Computing Surveys, Vol. 24, No. 4 (December 1992); Peterson, J. L., Computer Programs for Detecting and Correcting Spelling Errors, The Communications of the ACM, Volume 23, No. 12 (December 1980); and Daciuk, J., Spelling Correction in the paper Incremental Construction of Finite-State Automata and Transducers, and their Use in the Natural Language Processing (1998).
But classic spell-check techniques can only handle a certain number of differences between the typed word and the intended correct word. Because the best correction candidate is presumed to be the one with the fewest changes, spell-check algorithms are confounded by, for example, unknowing shifting of fingers by a typist on the keyboard, or tapping on a touch screen keyboard hurriedly and inaccurately, and thus typing almost every letter wrong.
To limit the amount of computational processing, particularly on lower-performance mobile devices, implementations of the classic algorithms make assumptions or impose constraints to reduce the ambiguity and thus the number of candidate words being considered. For example, they may rely on the initial letters of the word being correct or severely limit the size of the vocabulary.
Another form of automatic error correction, useful both for keyboards on touch-sensitive surfaces and for standard phone keypads, calculates the distances between each input location and nearby letters and compares the entire input sequence against possible words. The word whose letters are the closest to the input locations, combined with the highest frequency and/or recency of use of the word, is the best correction candidate. This technique easily corrects both shifted fingers and hurried tapping. It can also offer reasonable word completions even if the initial letters are not all entered accurately.
The following patent publications describe the use of a “SloppyType” engine for disambiguating and auto-correcting ambiguous keys, soft keyboards, and handwriting recognition systems: Robinson; B. Alex, Longe; Michael R., Keyboard System With Automatic Correction, U.S. Pat. No. 6,801,190 (Oct. 5, 2004), U.S. Pat. No. 7,088,345 (Aug. 8, 2006), and U.S. Pat. No. 7,277,088 (Oct. 2, 2007); Robinson et al, Handwriting And Voice Input With Automatic Correction, U.S. Pat. No. 7,319,957 (Jan. 15, 2008), and U.S. patent application Ser. No. 11/043,525 (filed Jan. 25, 2005). See also, Vargas; Garrett R., Adjusting keyboard, U.S. Pat. No. 5,748,512 (May 5, 1998).
In addition, the following publications cover combinations of manual and vocal input for text disambiguation: Longe, et al., Multimodal Disambiguation of Speech Recognition, U.S. patent application Ser. No. 11/143,409 (filed Jun. 1, 2005); and Stephanick, et al, Method and Apparatus Utilizing Voice Input to Resolve Ambiguous Manually Entered Text Input, U.S. patent application Ser. No. 11/350,234 (filed Feb. 7, 2006).
The “Sloppy Type” technology referenced above uses distance-based error correction on full words. Assuming that the length of the input sequence equals the length of the intended word and that each input location is in the proper order helps compensate for the increased ambiguity introduced by considering multiple nearby letters for each input. But in addition to minor targeting errors, people also transpose keys, double-tap keys, miss a key completely, or misspell a word when typing.
It would be advantageous to provide a mechanism for addressing all forms of typing errors in a way that offers both accurate corrections and acceptable performance.